package violentRecursion;

/**
 * @className: LeetCode_123
 * @Description: 买卖股票的最佳时机 IV
 * @author: kunkun
 * @date: 2025/7/10 21:07
 *
 */
public class LeetCode_188 {
    public int maxProfit(int k, int[] prices) {
        return solution_2(prices,0,k,true);
    }

    private int solution_2(int[] prices, int x, int k1, boolean b) {
        int[][] dp1=new int[prices.length+1][k1+1];       //true
        int[][] dp2=new int[prices.length+1][k1+1];        //false
        for (int i = prices.length-1; i >= 0; i--) {
            for (int k = k1; k >= 0; k--) {
                dp1[i][k]=Math.max(
                        (k>0)?dp2[i+1][k-1]-prices[i]:Integer.MIN_VALUE,dp1[i+1][k]);
                dp2[i][k]=Math.max(dp1[i+1][k]+prices[i],dp2[i+1][k]);
            }
        }
        return dp1[0][k1];
    }
}
